package dp.一维数组;


import java.util.Arrays;

/**
 *  https://leetcode.cn/problems/coin-change/
 *
 *  题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493719&idx=1&sn=edfeed0628a26fd665a105fa003bfaa2&chksm=9bd4165faca39f49946dcbe3f2b98f3a2eb5fa0efe980ebf904d2dce6841f5f6241c149ef80f&scene=178&cur_album_id=2165170016067944448#rd
 */
public class _322_零钱兑换 {

    int[] meno;

    int[] coins;

    public int coinChange(int[] coins, int amount) {
        this.meno = new int[amount + 1];
        Arrays.fill(meno, -2);
        this.coins = coins;
        return dp(amount);
    }

    private int dp(int n) {
        if (n < 0) return -1;
        if (n == 0) return 0;

        if (meno[n] != -2) return meno[n];

        int res = Integer.MAX_VALUE;

        for (int coin : coins) {
            int subProblem = dp(n - coin);
            if(subProblem == -1) {
                continue;
            }
            res = Math.min(res, subProblem + 1);
        }

        if(res == Integer.MAX_VALUE) {
            meno[n] = -1;
        }else {
            meno[n] = res;
        }

        return meno[n];
    }

}
